tg-me.com/knowledge_accumulator/282
Last Update:
Магия квантовых компьютеров
Моя любимая теория заговора состоит в том, что на самом деле физики знают, что практическая реализация квантового компьютера, который будет приносить реальную пользу, невозможна. Они распространили мифы о квантовых вычислениях, обещая светлое будущее, но всё это продуманный скам с целью десятилетиями распиливать бабло на его "исследовании". Квантовые компьютеры - это AGI из 90-х, но лучше, потому что непонятны широкой публике и не вызывают сумасшедших ожиданий к 2027-му.
Я плохо понимаю суть вопроса, но, увидев видео про квантовые вычисления от 3Blue1Brown, решил, что, может быть, пора разобраться, развеять мифы в своей голове и заодно поведать это дорогим подписчикам.
Физический компьютер - это практическая реализация вычислений в каких-то абстракциях. В классическом такой абстракцией являются биты, тогда как в квантовом они другие. То, как эти абстракции реализованы физически - это отдельная сложная тема, для начала необходимо понять то, в чём, собственно, суть выполняемых расчётов.
В квантовых вычислениях существуют разные алгоритмы, крайне сильно отличающиеся друг от друга. В упомянутом видео разбирался алгоритм Гровера, который может быть использован для решения NP-задач. Рассмотрим примитивнейшую постановку, в которой он может быть применён.
У вас есть произвольная программа, который получает бинарную строку размером N, и выдаёт 1 только для одной из них, которую вы и должны отыскать. На обычном компьютере ничего лучше подавания в неё всех 2^N вариантов сделать нельзя, зато, если вы знаете ответ, вы можете легко проверить его за одно применение.
Алгоритм Гровера позволяет решить эту задачу гораздо быстрее, но не за полиномиальное время, как вы могли бы подумать, а всего лишь за sqrt(2^N), то есть за экспоненту в 2 раза меньше. Алгоритм Гровера - это буквально плазменная колода из Balatro.
Теперь нам необходимо погрузиться в сам фреймворк вычислений, чтобы понять его суть. Пока нам придётся поверить на слово в то, что эти абстракции так работают, но в целом я пока не увидел в них ничего магического, так что сойдёт.
Квантовые вычисления происходят над кубитами - ячейками, способная принимать произвольное значение от 0 до 1. N обычных бит могут закодировать 2^N возможных состояний, а N кубитов кодируют вектор на единичной сфере в пространстве размерности 2^N - назовём его состоянием.
Первое правило квантового клуба - если у вас есть классический алгоритм, выдающий 1 для одной из 2^N бинарных строк, то у него есть альтер-эго в квантовом фреймворке. В нём он получает на вход вектор состояния размерности 2^N, и ровно у одной компоненты, соответствующего правильному ответу, умножает значение на -1.
Второе правило квантового клуба - если у нас есть вектор состояния, то мы можем его симметрично отразить относительно вектора [1/sqrt(2^N), 1/sqrt(2^N), ..., 1/sqrt(2^N)] - назовём его вектором равного состояния.
Итак, алгоритм Гровера состоит в том, что мы берём вектор равного состояния и начинаем применять к нему в цикле две описанные выше операции по очереди. После каждого раза вектор состояния становится ближе к базисному вектору, соответствующему правильному ответу. Скорость прииближения в радианах - 1/sqrt(2^N) за прокрутку. Таким образом, применив его pi/4 * sqrt(2^N) раз, наш вектор состояния станет очень близким к правильному ответу, и только в этот момент будет смысл его прочитать.
3Blue1Brown говорит, что миф о том, что квантовый компьютер каким-то магическим образом проверяет все ответы за раз, неверен. В случае алгоритма Гровера имеет смысл другая аналогия. Представьте, что вы находитесь в вершине N-мерного гиперкуба и пытаетесь попасть в его противоположный конец. Обычный компьютер позволяет вам ходить лишь по рёбрам куба, а вот алгоритм Гровера позволяет вам идти прямо к цели, и суммарное расстояние уменьшится до sqrt(N).
Мне ещё предстоит разобраться в других квантовых алгоритмах. Насколько я понял, алгоритм Шора, раскладывающий числа на простые множители, действительно обещает нам экспоненциальный прирост в скорости. Но это в другой раз.
@knowledge_accumulator
BY Knowledge Accumulator
Share with your friend now:
tg-me.com/knowledge_accumulator/282